{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 1. Genetic Algorithm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Genetic Algorithm (GA) is a computing technique based on Darwinian evolution. To use this, you start with a population of random guesses, rank them based on some fitness score, make small adjustments over time, and select the best at each generation. Over time, you can evolve anything, given that it can have a score associated with it.\n", "\n", "In this experiment, we will evolve a picture of Taylor Swift. That is, we will evolve (using simulated selection, mutation, and mating) a program that can generate a picture of Taylor Swift. Why? This is largely an example of using arrays, and to show that computers can find unique solutions to problems." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#Table of Contents\n", "* [1. Genetic Algorithm](#1.-Genetic-Algorithm)\n", "\t* [1.1 \"Information\"](#1.1-\"Information\")\n", "\t* [1.2 Genotype](#1.2-Genotype)\n", "\t* [1.3 Fitness](#1.3-Fitness)\n", "\t* [1.4 Evolve](#1.4-Evolve)\n", "\t* [1.5 Results](#1.5-Results)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.1 \"Information\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Creating this kind of representation of an image could also be practical. For example, a 100 x 100 pixel image contains 100 x 100 x 4 x 8 (320,000) _bits of information_. If we could reduce that to 50 x 7 x 8 (2,800) _bits of information_, that would be quite a savings (0.8 % of the original size)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For this experiment, we will need a target image. Here is an image that is 100 pixels by 100 pixels:" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Downloaded 'taylor_swift.jpg'.\n" ] } ], "source": [ "%download http://www.avatarsdb.com/avatars/taylor_swift.jpg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will attempt to evolve this image." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.2 Genotype" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The genotype will be composed of 50 random circles of a particular color (including red, green, blue, and alpha components) and a particular radius, at a given x,y location. So each genotype is made up of 50 of these:\n", "\n", "* red\n", "* green\n", "* blue\n", "* alpha\n", "* radius\n", "* x\n", "* y\n", "\n", "So, a genotype is 50 x 7, or 350 numbers. Each value will be represented by a number between 0 and 1, and will be scaled appropriately for its use. Every 7 values (gene) will be used to draw one circle.\n", "\n", "We draw each of the 50 circles to get an image like the following. Here we will draw the image that the genotype represents (the phenotype) on a PGraphics object, and then at the end render it to the Sketch.\n", "\n", "Note that to use a PGraphics object, we call `createGraphics()` with width and height as arguments. Then, we call `pg.fill()`, `pg.noStroke()`, and `pg.ellipse()`. These are just like `fill()`, `noStroke()`, and `ellipse()` but they work on the PGraphics object, rather than on the canvas.\n", "\n", "At some point later, we call `image(pg, 0, 0)` which says to make an image out of the PGraphics object, and draw it at (0, 0). " ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "
\n", "Original/target\n", " | \n", "\n", "1 Hour\n", " | \n", "\n", "2 Hours\n", " | \n", "\n", "10 Hours\n", " | \n", "
---|---|---|---|
\n", " \n", " | \n", "\n", " \n", " | \n", "\n", " \n", " | \n", "\n", " \n", " | \n", "